package com.cat.dynamicPlanning02;

import java.util.Arrays;

/**
*   @description https://leetcode.cn/problems/can-i-win/
*   @author 曲大人的喵
*   @create 2025/11/5 12:30
*   @since JDK17
*/

public class Solution37 {
    static int N = 1 << 20;
    static int[] dp = new int[N];
    int n;
    boolean dfs(int status, int rest) {
        if (rest <= 0) {
            return false;
        }
        if (dp[status] != 0) {
            return dp[status] == 1 ? true : false;
        }
        boolean ans = false;
        for (int i = 1; i <= n; i++) {
            if ((status >> i & 1) == 1 && !dfs(status ^ (1 << i), rest - i)) {
                ans = true;
                break;
            }
        }
        dp[status] = ans ? 1 : -1;
        return ans;
    }

    public boolean canIWin(int n, int m) {
        this.n = n;
        Arrays.fill(dp, 1, 1 << n, 0);
        return dfs((1 << n) - 1, m);
    }
}
